#include <pthread.h>
#include <iostream>
#include <cstdio>
#include <unistd.h>
#include <string>
#include <ctime>

using namespace std;

//因为多个线程是共享地址空间的,也就是很多的资源都是共享的
//这样的优点就是线程和线程之间的通信非常方便
//这样的缺点就是线程和线程之间缺乏访问控制
//线程安全问题:因为一个线程的操作问题,给其他线程造成了不可控,或者引起崩溃,异常,逻辑不正确等这种现象
//创建一个线程如果想要避免线程安全问题,尽量避免使用全局,STL,malloc,new等在全局有效的数据
//如果要使用这些关键字的话,需要对这些数据进行访问控制
//所以这些访问控制就引出了同步和互斥

//进程线程间的互斥相关背景概念
// 1.临界资源:多个线程执行流共享的资源就叫做临界资源(多线程/多进程打印数据到显示器上{这个时候显示器就是临界资源})
// 2.临界区:每个线程内部,访问临界资源的代码,就叫做临界区
// 3.对临界区进行保护的方式:互斥和同步,本质就是对临界资源的保护
// 4.互斥:任何时刻,互斥保证有且只有一个执行流进入临界区,访问临界资源,通常对临界资源起保护作用
// 5.同步:一般而言,让访问临界资源的过程在安全的前提下(一般是互斥和原子性的),让访问资源具有一定的顺序性
// 6.原子性:不会被任何调度机制打断的操作,该操作只有两种状态,要是完成的,要么没有完成

//互斥
//大部分情况,下,线程使用的数据都是局部变量,变量的地址空间在线程栈空间内
//这种情况,变量归属于单个线程,其他线程无法获得这种变量
// 有时,很多变量都需要在线程间共享,这样的变量称为共享变量,可以通过数据的共享,完成线程之间的交互
// 多个线程并发的操作共享变量,可能会带来一些问题

//我们下面编写一个程序,来模拟多个线程并发操作共享变量,可能带来的一些问题
//比如抢票系统,可以把票抢到负数
//为什么可能把票抢到负数?
// 1.if语句判断条件为真以后,代码可以并发的切换到其他线程
// 2.usleep这个模拟漫长业务的过程中,可能会有很多个线程进入该代码段

//我们这里也可以顺便认识一下,--_tickets操作不是一个原子操作(一条汇编指令)
//这个操作可以对应三条汇编指令
// 1.load:将共享变量_tickets从内存加载到寄存器中
// 2.update:更新寄存器里面的值,执行-1的操作
// 3.store:将新的值从寄存器写回共享变量_tickets的内存地址

class ticket
{
public:
    ticket()
        :_tickets(50000000)
    {}

    bool get_ticket()
    {
        bool res = true;
        if (_tickets > 0)
        {
            //虽然_tickets > 0,但是这个时候休眠,其他线程也会进来
            //一个线程修改了_tickets,变为了0,其他的线程也会进行_tickets的修改
            //所以会造成资源的问题
            //usleep(1000);
            cout << "我是线程[" << pthread_self() << "]我抢的票是:" << _tickets << endl;
            --_tickets;

            //为什么这里设置休眠时间,从运行的结果来看,不会产生资源问题
            //因为线程进来就说明这个时候_tickets是大于0的,然后就直接了抢票,动作是很快的
            //当_tickets为1的时候,一个线程进来,立马抢到了票,_tickets变为了0
            //其他的线程在进行usleep,然后就进不来了
            //所以不会产生资源问题
            //usleep(1000);
        }
        else
        {
            res = false;
            cout << "我是线程["<< pthread_self() << "]" << "票已经被抢空了!" << endl;

        }
        return res;
    }

private:
    int _tickets;
};

void* thread_routine(void* arg)
{
    ticket* t = (ticket* )arg;
    while(true)
    {
        if(!t->get_ticket())
        {
            break;
        }
    }
}

int main()
{
    ticket* t = new ticket();

    pthread_t tid[5];
    for (int i = 0; i < sizeof(tid) / sizeof(tid[0]); ++i)
    {
        pthread_create(tid + i, nullptr, thread_routine, (void* ) t);
    }

    for (int i = 0; i < sizeof(tid) / sizeof(tid[0]); ++i)
    {
        pthread_join(tid[i], nullptr);
    }
    return 0;
}

//我们要解决以上代码产生的这些问题,需要做到以下几点:
// 1.代码必须要有互斥行为:当代码进入临界区执行时,不允许其他线程进入该临界区
// 2.如果多个线程同时要求执行临界区的代码,并且临界区没有线程在执行,那么只允许一个线程进入该临界区
// 3.如果线程不在临界区中执行,那么该线程不能阻止其他线程进入临界区

//要做到这三点,本质就是一把锁,Linux上提供的这把锁叫做互斥量,效果可以形象如下
//              非临界区,可以并发执行代码
//                       lock
//      临界区,只允许一个线程执行,不允许多个线程同时执行
//                       unlock
//              非临界区,可以并发执行代码

// 互斥量的接口:
// 初始化互斥量的两种方法:
// 1.静态分配
// pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// 2.动态分配
// pthread_mutex_init函数
// 功能:
//     初始化互斥量
// 原型:
//     int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrictattr);
// 参数:
//     mutex:需要进行初始化的互斥量
//     attr:设置这个互斥量的属性,nullptr为默认的属性
// 返回值:
//     成功返回0,失败返回错误码

// 互斥量加锁
// pthread_mutex_lock函数
// 功能:
//     将指定的互斥量进行加锁
// 原型:
//     int pthread_mutex_lock(phtread_mutex_t* mutex);
// 参数:
//     mutex:一个互斥量的地址
// 返回值:
//     成功返回0,失败返回错误码
// PS:
//     1.互斥量处于未锁状态,该函数将互斥量锁定,同时返回成功
//     2.发起函数调用时,其他线程已经锁定互斥量,或者存在其他线程同时申请互斥量,但是没有竞争到互斥量
//     那么pthead_lock调用会陷入阻塞(执行流被挂起),等待互斥量解锁

// 互斥量解锁
// pthread_mutex_unlock函数
// 功能:
//     将指定的互斥量进行解锁
// 原型:
//     int pthread_mutex_unlock(phtread_mutex_t* mutex);
// 参数:
//     mutex:一个互斥量的地址
// 返回值:
//     成功返回0,失败返回错误码

// 销毁互斥量
// pthread_mutex_destroy函数
// 功能:
//     将指定的互斥量进行解锁
// 原型:
//     int pthread_mutex_destroy(pthread_mytex_t* mutex);
// 参数:
//     mutex:一个互斥量的地址
// 返回值:
//     成功返回0,失败返回错误码
// PS:
//     1.使用PTHREAD_MUTEX_INITIALIZER初始化的互斥量不需要销毁
//     2.一个销毁一个已经加锁的互斥量
//     3.已经销毁的互斥量,要确保后面不会有线程在尝试加锁

//那么我们引入互斥量,重新修改上面的售票系统,解决资源共享的一些问题


// class ticket
// {
// public:
//     ticket()
//         : _tickets(1000)
//     {
//         pthread_mutex_init(&_mutex, nullptr);
//     }

//     ~ticket()
//     {
//         pthread_mutex_destroy(&_mutex);
//     }

//     bool get_ticket()
//     {
//         bool res = true;
//         //    我要访问临界资源的时候_tickets,需要先访问mutex
//         //    这个mutex是所有线程都必须先看到它
//         //    那么互斥量本身就是临界资源
//         //    那么如何保证锁本身是安全的?
//         //    因为lock 和 unlock操作都是原子的,具体理由查看下方解释


//         //    加锁的区域,只有我这个线程可以执行,其他线程不能执行
//         //    就算因为时间片被切换走了,也是把锁带走的,不把加锁区域的任务执行完成,是不会解锁的
//         //    在其他的线程的眼里,这个线程的操作要么是没有做的,要么是做完的,也就是完成了操作的原子性
//         //    执行这部分代码的执行流是互斥的,串行执行的
//         pthread_mutex_lock(&_mutex);
//         if (_tickets > 0)
//         {
//             usleep(1000);
//             cout << "我是线程[" << pthread_self() << "]我抢的票是:" << _tickets << endl;
//             --_tickets;
//         }
//         else
//         {
//             res = false;
//             cout << "我是线程["<< pthread_self() << "]" << "票已经被抢空了!" << endl;
//         }
//         pthread_mutex_unlock(&_mutex);

//         usleep(((rand() % 11) * 1000));

//         return res;
//     }

// private:
//     int _tickets;
//     pthread_mutex_t _mutex;
// };

// void *thread_routine(void *arg)
// {
//     ticket *t = (ticket *)arg;
//     int count = 0;
//     while (true)
//     {
//         count++;
//         if (!t->get_ticket())
//         {   
//             break;
//         }
//     }
//     usleep(10000);
//     cout << "我是线程[" << pthread_self() << "]我总共抢到了:" << count  << "张票" << endl;

// }

// int main()
// {
//     srand((long long)time(nullptr));
//     ticket *t = new ticket();

//     pthread_t tid[5];
//     for (int i = 0; i < 5; ++i)
//     {
//         pthread_create(tid + i, nullptr, thread_routine, (void *)t);
//     }

//     for (int i = 0; i < 5; ++i)
//     {
//         pthread_join(tid[i], nullptr);
//     }
//     return 0;
// }

//下面我们来探讨一下互斥量的实现原理
//这是lock和unlock的伪代码
// lock:
//     movb $0, %al
//     xchgb %al, mutex
//     if (al寄存器的内容 > 0)
//     {
//         return 0;
//     }
//     else
//     {
//         挂起等待;
//     }
//     goto lock;

// unlock:
//     movb $1, mutex
//     唤醒等待mutex的线程
//     return 0;

//我们初始化一个互斥量的时候,这个互斥量里面用来标识的int设置为1,标识未加锁
//经过上面的例子，大家已经意识到单纯的 i++ 或者 ++i 都不是原子的,有可能会有数据一致性问题
// 为了实现互斥锁操作,大多数体系结构都提供了swap或exchange指令,该指令的作用是把寄存器和内存单
// 元的数据相交换,由于只有一条指令,保证了原子性,即使是多处理器平台,访问内存的 总线周期也有先后,一
// 个处理器上的交换指令执行时另一个处理器的交换指令只能等待总线周期

//当多个线程拿到这个互斥量,进行上锁的时候,总有一个线程先执行movb $0, %al
//也就意味着对al寄存器赋值0,然后执行xchgb %al, mutex,将mutex里面的1和al寄存里面的0,进行了互换
//使用一行汇编代码,原子性的完成了共享的内存数据mutex,交换到这个线程上下文中,从而实现了私有的过程
//当其他的线程执行xchgb %al, mutex,就是将mutex里面的0和al寄存里面的0,进行了互换
//然后下面if (al寄存器的内容 > 0),就会只有一个线程进入,成功返回0
// 而其他的线程进入else,就等待挂起了.
// 当mutex解锁的时候,执行movb $1, mutex,mutex的值也就恢复为1了,然后唤醒其他挂起等待mutex的线程
// 其他唤醒的线程继续执行goto lock
// 因为唤醒也是有成本的,所以这个时候
// 如果之前使用过上锁的mutex的线程还要继续上锁,那么其他线程一般是竞争不过这个线程的
// 如果这个线程的时间片到了,被切换出去了,其他的线程才会有机会去抢夺这把锁

//我们的线程在执行临界区里面代码,如果时间片到了,线程是可能被切走的
// 那么线程被切换走的时候,会进行上下文保护,而锁的数据也是在上下文中
// 也就是说被切换走的线程是抱着锁走的,这个时候正在申请锁的线程,继续被挂起等待
// 而其他的线程这个时候想要申请锁,是不可能成功的,休想进入临界区
// 在其他线程的视角,对于其他线程有意义的状态,要么是这个线程没有使用锁,要么是这个线程使用完了锁
// 所以可以保证这个线程访问临界区的原子性

// 代码是程序员写的,为了保证临界区的安全
// 必须保证使用这个临界区的其他线程遵守相同的"编码规范"
// 这个线程申请锁,其他线程也需要申请锁

//下面我们对可重入和线程安全做一个区分
// 概念:
// 线程安全:
//     多个线程并发同一段代码时,不会出现不同的结果,常见对全局变量或者静态变量进行操作
//     并且没有锁保护的情况下,会出现该问题
// 重入:
//     同一个函数被不同的执行流调用,当前一个流程还没有执行完,就有其他的执行流再次进入
//     我们称之为重入.一个函数在重入的情况下,运行结果不会出现任何不同或者任何问题
//     则该函数被称为可重入函数,否则是不可重入函数

// 常见的线程不安全的情况:
// 1.不保护共享变量的函数
// 2.函数状态随着被调用,状态发生改变的函数
// 3.返回指向静态变量指针的函数
// 4.调用线程不安全函数的函数

// 常见的线程安全的情况:
// 1.每个线程对全局变量或者静态变量只有读取的权限,而没有写入权限,一般来说这些线程是安全的
// 2.类或接口对于线程来说都是原子操作
// 3.多个线程之间的切换不会导致该接口的执行结果存在二义性

// 常见不可重入的情况:
// 1.调用了malloc/free函数,因为malloc函数使用全局链表来管理堆的
// 2.调用标准I/O库函数,标准I/O库的很多实现都以不可重入的方式使用全局数据结构
// 3.可重入函数体内使用了静态的数据结构

// 常见可重入的情况
// 1.不使用全局变量或静态变量
// 2.不使用malloc或者new开辟出的空间
// 3.不调用不可重入函数
// 4.不返回静态或全局数据,所有数据都有函数的调用者提供
// 5.使用本地数据,或者通过制作全局数据的本地拷贝来保护全局数据

// 可重入与线程安全联系
// 1.函数是不可冲入的,那就是线程安全的
// 2.函数如果是不可重入的,那就不能由多个线程使用,否则可能引发线程安全问题
// 3.如果一个函数中有全局`变量,那么这个函数既不是线程安全也不是可重入的

// 可重入与线程安全区别
// 1.可重入函数是线程安全函数的一种
// 2.线程安全不一定是可重入的,而可重入函数则一定是线程安全的
// 3.如果将对临界资源的访问加上锁,则这个函数是线程安全的
// 但如果锁还没有释放,再次重入这个函数,那么就会产生死锁,因此是不可重入的

//下面我们来了解一下死锁的相关概念
//参考的文章地址
//https://blog.csdn.net/tonychan129/article/details/126295081
//什么是死锁?
// 所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局
// 当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进
// 因此我们举个例子来描述
// 如果此时有一个线程A，按照先锁a再获得锁b的的顺序获得锁
// 而在此同时又有另外一个线程B，按照先锁b再锁a的顺序获得锁
// 那么这种情况就会造成死锁

// 产生死锁的原因？
// 可归结为如下两点：
// a. 竞争资源
// 系统中的资源可以分为两类：
// 可剥夺资源,是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU和主存均属于可剥夺性资源；
// 另一类资源是不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。
// 产生死锁中的竞争资源之一指的是竞争不可剥夺资源
// 例如：系统中只有一台打印机,可供进程P1使用，假定P1已占用了打印机，若P2继续要求打印机打印将阻塞
// 产生死锁中的竞争资源另外一种资源指的是竞争临时资源（临时资源包括硬件中断、信号、消息、缓冲区内的消息等）
// 通常消息通信顺序进行不当，则会产生死锁

// b. 进程间推进顺序非法
// 若P1保持了资源R1,P2保持了资源R2，系统处于不安全状态，因为这两个进程再向前推进，便可能发生死锁
// 例如，当P1运行到P1：Request（R2）时，将因R2已被P2占用而阻塞；当P2运行到P2：Request（R1）时，也将因R1已被P1占用而阻塞，于是发生进程死锁

// 死锁产生的4个必要条件:
// 互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
// 请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
// 不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
// 环路等待条件：在发生死锁时，必然存在一个进程–资源的环形链。

// 解决死锁的基本方法
// 预防死锁：
// 资源一次性分配：一次性分配所有资源，这样就不会再有请求了：（破坏请求条件）
// 只要有一个资源得不到分配，也不给这个进程分配其他的资源：（破坏请保持条件）
// 可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）
// 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）

